package com.code.test.second.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.md
 * <p>
 * 40.组合总和II
 * 力扣题目链接
 * <p>
 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * <p>
 * candidates 中的每个数字在每个组合中只能使用一次。
 * <p>
 * 说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合。
 * <p>
 * 示例 1:
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * 所求解集为:
 * [
 * [1, 7],
 * [1, 2, 5],
 * [2, 6],
 * [1, 1, 6]
 * ]
 * 示例 2:
 * 输入: candidates = [2,5,2,1,2], target = 5,
 * 所求解集为:
 * [
 * [1,2,2],
 * [5]
 * ]
 */
public class SCode40 {


    public static void main(String[] args) {
        int[] nums = {10, 1, 2, 7, 6, 1, 5};
        List<List<Integer>> ret = combine(nums, 8);
        System.out.println(ret.size());
        System.out.println(ret);
    }


    static List<List<Integer>> ret = new ArrayList<>();
    //每个组合
    static List<Integer> temp = new ArrayList<>();

    static boolean[] used = new boolean[10];

    public static List<List<Integer>> combine(int[] nums, int targetSum) {
        Arrays.sort(nums);
        Arrays.fill(used, false);
        back(nums, targetSum, 0);
        return ret;
    }

    /**
     * 有重复元素
     * target = [任意数量组合]
     * 不能包含重复组合
     * 每个数字只能在单个组合中使用一次，但是数组内可以有多个重复数字，比如[1,1,2]
     * 1<=candidates[i]<=200
     */

    /**
     * 解题：
     * 递归层次未知，因为可以任意组合
     * <p>
     * List<List<Integer>> ret 最终结果
     * List<Integer> 单个组合
     */

    public static void back(int[] nums, int targetSum, int startIndex) {
        int sum = temp.stream()
                .mapToInt(Integer::intValue)
                .sum();
        if (targetSum == sum) {
            ret.add(new ArrayList<>(temp));
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            int cur = nums[i];
            //已经>=targetSum，要过滤掉
            if (sum + cur > targetSum) {
                continue;
            }
            /**
             * 数组已经排过序
             * 因为相同元素不能在下一个分支上使用，所以要先过滤掉
             */
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                /**
                 * 如果前一个没有使用
                 * [1,1,2]
                 *
                 */
                continue;
            }
            temp.add(cur);
            used[i] = true;
            /**
             * 这里i+1是因为不能包含自身，要往子集找
             */
            back(nums, targetSum, i + 1);
            used[i] = false;
            temp.remove(temp.size() - 1);
        }
    }


}
